package pers.vic.basics.leetcode;

import java.util.*;

/**
 * @author Vic.xu
 * @description: 47. 全排列 II {@literal https://leetcode-cn.com/problems/permutations-ii/}
 * @date: 2020/12/10 0010 8:53
 */
public class J0047_M_PermuteUnique {
    /*
    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     */

    /**
     * 这一题和46题基本一致，唯一的区别是数字的序列有重复，返回的是不能重复的全排列
     * 简单的做法，肯定是用Set直接去重，但是这样肯定不是题目的意义所在，
     * 通过边界条件作为判断依据应该才是需要做的
     * 1 1 2 2
     * 1 2 1 2
     * 1 2 2 1
     * 2 2 1 1
     * 2 1 2 1
     * 2 1 1 2
     * 可以看出由于重复数字在相同位置罗列的时候 不应该重复出现
     * 比如当1 作为首位 排列完之后  再次排列首位的时候 就不能使用重复项1
     * 当2 作为第二位罗列完之后，再次排列第二位的时候 就不能使用2
     * 也即，同一层的选择不能出现重复
     */
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> temp = new ArrayDeque<>();
        int len = nums.length;
        boolean[] used = new boolean[len];
        backtracking(nums, res, temp, len, used);
        return res;
    }

    /**
     * 同一层的选择不能出现重复：当前位置的数字在上一次中已经重复使用过了
     */
    public static void backtracking(int[] nums, List<List<Integer>> res, Deque<Integer> temp, int len, boolean[] used) {
        if (temp.size() == len) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i] == true) {
                continue;
            }
            //当前数字 在当前位置已经使用
            if (i > 0 &&  nums[i-1] == nums[i] && used[i-1]) {
                continue;
            }
            temp.add(nums[i]);
            used[i] = true;
            backtracking(nums, res, temp, len, used);
            used[i] = false;
            temp.removeLast();

        }
    }

    public static void main(String[] args) {
        permuteUnique(new int[]{1,1,2,2}).forEach(System.out::println);
    }
}
